/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/jump-game-ii
   @Language: C++
   @Datetime: 19-06-19 14:22
   */

class Solution {
public:
	int jump(vector<int> &nums) {
		int step=0;
		for(int i=0, maxpos=0, curpos=0; i<nums.size(); ++i){
			if (i>maxpos) return -1;
			if (i>curpos){  // need jump
				curpos = maxpos;
				++step;
			}
			maxpos = max(maxpos,i+nums[i]);
		}
		return step;
	}
};
